"""
新问题：最小路径和
这是一个经典的动态规划问题，要求我们从网格的左上角出发，到达右下角时，路径上的数字和最小。你只能向右或向下移动。

问题描述：
给定一个 m×n 的网格 grid，其中每个位置都有一个非负整数。你从左上角开始，只能向右或向下走，求从起点到终点的路径上数字之和的最小值。
"""
def min_path_sum(grid):
    m, n = len(grid), len(grid[0])
    # 创建 dp 表格,dp[i][j]表示按照既定规则走到i行j列最少的路径和
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    # dp表的第一行，第一列，只能向右走或者向下走，所以只有一种情况，故可以直接写出来
    # 初始化dp的第一行
    for j in range(1,n):
        dp[0][j] = dp[0][j-1]+grid[0][j]
    # 初始化dp的第一列
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    # 填完剩下的格子
    for i in range(1,m):
        for j in range(1,n):
            """
            有两种情况,比较这两种情况哪种小,并选择小的
            1,向左走dp[i][j] = dp[i][j-1]+grid[i][j]
            2,向右走dp[i][j] = dp[i-1][j]+grid[i][j]
            """
            dp[i][j] = min(dp[i-1][j]+ grid[i][j],dp[i][j-1]+ grid[i][j])
    print(dp[m-1][n-1],dp)
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
result = min_path_sum(grid)
print(result)  # 输出：7